# 广度优先搜索

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        tmpque = collections.deque([root])
        ans = []
        while tmpque:
            count = len(tmpque)
            total = 0
            for _ in range(count):
                tmp = tmpque.popleft()
                total += tmp.val
                if tmp.left:
                    tmpque.append(tmp.left)
                if tmp.right:
                    tmpque.append(tmp.right)
            ans.append(total/count)
        return ans